package com.test27_二叉树;

/**
 * 二叉树的实现类
 */
public class BinaryTreeImpl<E> implements IBinaryTree<E> {
    /** 内部节点类 */
    private class Node {
        private Comparable<E> data;
        private Node left;  // 左子树
        private Node right; // 右子树
        private Node parent;    // 父节点

        public Node(Comparable<E> data) {
            this.data = data;
        }

        public void toArrayNode() {
            if (this.left != null) {
                this.left.toArrayNode();    // 递归调用
            }
            BinaryTreeImpl.this.data[BinaryTreeImpl.this.foot++] = (E) this.data;
            if (this.right != null) {
                this.right.toArrayNode();   // 递归调用
            }
        }

        public Node containsNode(E data) {
            if (this.data.compareTo(data) == 0) {   // 数据相同，返回当前节点
                return this;
            } else {
                if (this.data.compareTo(data) < 0) {    // 继续查询右节点
                    if (this.right != null) {
                        return this.right.containsNode(data);
                    }
                } else {    // 继续查询左节点
                    if (this.left != null) {
                        return this.left.containsNode(data);
                    }
                }
            }
            return null;
        }
    }
    // ================= 二叉树实现的相关处理操作 =================
    private Node root;  // 根节点
    private int count;  // 保存数据个数
    private int foot;       // 描述数组的索引
    private Object[] data;  // 返回的对象数组

    /** 数据添加 */
    @Override
    public void add(E data) {
        if (data == null) {
            throw new NullPointerException("存储在二叉树结构中的数据不允许为null");
        }
        if (!(data instanceof Comparable)) {
            throw new ClassCastException("要保存数据对象所在的类没有实现Comparable接口");
        }
        Node newNode = new Node((Comparable) data);     // 将数据保存在节点之中
        if (this.root == null) {
            this.root = newNode;    // 保存根节点
        } else {    // 需要确定节点的存储位置
            Node currentNode = this.root;
            while (currentNode != newNode) {
                if (currentNode.data.compareTo(data) <= 0) {    // 比根节点大，放右边
                    if (currentNode.right != null) {
                        currentNode = currentNode.right;
                    } else {
                        currentNode.right = newNode;
                        newNode.parent = currentNode;   // 设置父节点
                        currentNode = newNode;  // 结束循环
                    }
                } else {    // 比根节点小，放左边
                    if (currentNode.left != null) {
                        currentNode = currentNode.left;
                    } else {
                        currentNode.left = newNode;
                        newNode.parent = currentNode;   // 设置父节点
                        currentNode = newNode;  // 结束循环
                    }
                }
            }
        }
        this.count++;
    }

    /** 获取元素个数 */
    @Override
    public int size() {
        return this.count;
    }

    /** 获取对象数组 */
    @Override
    public Object[] toArray() {
        if (this.size() == 0) {
            return null;
        }
        this.data = new Object[this.count]; // 实例化新的对象数组
        this.foot = 0;  // 角标清零
        this.root.toArrayNode();    // 获取所有节点数据
        return this.data;
    }

    /** 判断数据是否存在 */
    @Override
    public boolean contains(E data) {
        if (data == null) {
            throw new NullPointerException("存储在二叉树结构中的数据不允许为null");
        }
        if (!(data instanceof Comparable)) {
            throw new ClassCastException("要保存数据对象所在的类没有实现Comparable接口");
        }
        if (this.count == 0) {
            return false;
        }
        return this.root.containsNode(data) != null;    // 返回的节点不为空，存在数据
    }

    /** 删除数据 */
    @Override
    public void remove(E data) {
        if (data == null) {
            throw new NullPointerException("存储在二叉树结构中的数据不允许为null");
        }
        if (!(data instanceof Comparable)) {
            throw new ClassCastException("要保存数据对象所在的类没有实现Comparable接口");
        }
        if (this.contains(data)) {
            if (this.root.data.compareTo(data) == 0) {
                this.root = this.moveNode(data);
            } else {
                this.moveNode(data);
            }
            this.count--;
        }
    }

    /** 实现节点移动 */
    private Node moveNode(E data) {
        Node moveSubNode = null;
        Node deleteNode = this.root.containsNode(data);
        if (deleteNode == null) {   // 不存在删除节点
            return null;
        }
        // 情况一：要删除的节点没有任何子节点存在
        if (deleteNode.left == null && deleteNode.right == null) {
            if (deleteNode.parent != null) {
                if (deleteNode.parent.left == deleteNode) {
                    deleteNode.parent.left = null;
                } else if (deleteNode.parent.right == deleteNode) {
                    deleteNode.parent.right = null;
                }
            }
        }
        // 情况二：有一个子节点，那么直接删除，并用其子节点去顶替他
        if ((deleteNode.left != null && deleteNode.right == null) ||
                (deleteNode.left == null && deleteNode.right != null)) {
            if (deleteNode.left != null) {  // 存在删除节点的左节点
                moveSubNode = deleteNode.left;
            } else {    // 存在删除节点的右节点
                moveSubNode = deleteNode.right;
            }
            if (deleteNode.parent != null) {
                if (deleteNode.parent.left == deleteNode) {
                    deleteNode.parent.left = moveSubNode;
                }  else if (deleteNode.parent.right == deleteNode) {
                    deleteNode.parent.right = moveSubNode;
                }
            }
            moveSubNode.parent = deleteNode.parent;     // 修改父节点
        }
        // 情况三：待删除节点有两个子节点，就需要确定右子树中最小节点
        if (deleteNode.left != null && deleteNode.right != null) {
            moveSubNode = deleteNode.right;
            while (moveSubNode.left != null) {  // 找到右边的最左节点
                moveSubNode = moveSubNode.left;
            }
            /*if (moveSubNode.right != null) {    // 移动节点存在有右节点
                moveSubNode.parent.left = moveSubNode.right;
                moveSubNode.right.parent = moveSubNode.parent;
            } else {
                if (deleteNode.right != moveSubNode) {
                    moveSubNode.parent.left = null;
                }
            }*/
            moveSubNode.parent = deleteNode.parent;
            moveSubNode.left = deleteNode.left;
            if (deleteNode.right != moveSubNode) {
                moveSubNode.right = deleteNode.right;
            }
            if (deleteNode.parent != null) {
                if (deleteNode.parent.left == deleteNode) {
                    deleteNode.parent.left = moveSubNode;
                }
                if (deleteNode.parent.right == deleteNode) {
                    deleteNode.parent.right = moveSubNode;
                }
            }
        }
        return moveSubNode;     // 返回移动的子节点
    }
}
